package graph;

public class GraphApp {

    public static void main(String[] args) {
        Graph theGraph = new Graph();
        WeightedGraph weightedGraph = new WeightedGraph();
//        theGraph.addVertex('A');    // 0  (start for dfs)
//        theGraph.addVertex('B');    // 1
//        theGraph.addVertex('C');    // 2
//        theGraph.addVertex('D');    // 3
//        theGraph.addVertex('E');    // 4
//        theGraph.addVertex('F');    //5
//        theGraph.addVertex('G');    //6
//        theGraph.addVertex('H');    //7
//        theGraph.addVertex('I');    //8
//
//        theGraph.addEdge(0, 1);     // AB
//        theGraph.addEdge(0, 2);     // AC
//        theGraph.addEdge(0, 3);     // AD
//        theGraph.addEdge(0, 4);     // AE
//        theGraph.addEdge(1, 5);     //BF
//        theGraph.addEdge(3, 6);     //DG
//        theGraph.addEdge(5, 7);     //FH
//        theGraph.addEdge(6, 8);     //GI
        
//        theGraph.addVertex('A'); // 0 (start for mst)
//        theGraph.addVertex('B'); // 1
//        theGraph.addVertex('C'); // 2
//        theGraph.addVertex('D'); // 3
//        theGraph.addVertex('E'); // 4  
//        
//        theGraph.addEdge(0, 1); // AB
//        theGraph.addEdge(0, 2); // AC
//        theGraph.addEdge(0, 3); // AD
//        theGraph.addEdge(0, 4); // AE
//        theGraph.addEdge(1, 2); // BC
//        theGraph.addEdge(1, 3); // BD
//        theGraph.addEdge(1, 4); // BE
//        theGraph.addEdge(2, 3); // CD
//        theGraph.addEdge(2, 4); // CE
//        theGraph.addEdge(3, 4); //DE
        
//        theGraph.addVertex('A'); // 0
//        theGraph.addVertex('B'); // 1
//        theGraph.addVertex('C'); // 2
//        theGraph.addVertex('D'); // 3
//        theGraph.addVertex('E'); // 4
//        theGraph.addVertex('F'); // 5
//        theGraph.addVertex('G'); // 6
//        theGraph.addVertex('H'); // 7
//        
//        theGraph.addDirectedEdge(0, 3); // AD
//        theGraph.addDirectedEdge(0, 4); // AE
//        theGraph.addDirectedEdge(1, 4); // BE
//        theGraph.addDirectedEdge(2, 5); // CF
//        theGraph.addDirectedEdge(3, 6); // DG
//        theGraph.addDirectedEdge(4, 6); // EG
//        theGraph.addDirectedEdge(5, 7); // FH
//        theGraph.addDirectedEdge(6, 7); // GH
        
        weightedGraph.addVertex('A'); // 0
        weightedGraph.addVertex('B'); // 1
        weightedGraph.addVertex('C'); // 2
        weightedGraph.addVertex('D'); // 3
        weightedGraph.addVertex('E'); // 4
        weightedGraph.addVertex('F'); // 5
        // After adding vertex 'G', mst ouputs wrong tree
        weightedGraph.addVertex('G'); //6
        
        weightedGraph.addEdge(0, 1, 8); //AB
        weightedGraph.addEdge(0, 3, 4); //AD
        weightedGraph.addEdge(0, 6, 6); //AG
        weightedGraph.addEdge(1, 2, 10); //BC
        weightedGraph.addEdge(1, 3, 3); //BD
        weightedGraph.addEdge(1, 4, 7); //BE
        weightedGraph.addEdge(2, 3, 8); //CD
        weightedGraph.addEdge(2, 4, 5); //CE
        weightedGraph.addEdge(2, 5, 6); //CF
        weightedGraph.addEdge(3, 4, 12); //DE
        weightedGraph.addEdge(4, 5, 7); //EF

//        System.out.print("Visits in depth-first search way: ");
//        theGraph.dfs();             // depth-first search
//        System.out.println();
//        
//        System.out.print("Visits in breadth-first search way: ");
//        theGraph.bfs();
//        System.out.println();
//        System.out.print("Minimum spanning tree: ");
//        theGraph.mst();
//        System.out.println();
        
//        System.out.print("Topological sorting: ");
//        theGraph.topo();
//        System.out.println();
        
        System.out.print("Minimum spanning tree: ");
        weightedGraph.mst(); //output should be AD DB BE EC CF
        System.out.println();
    }// end main()
}
